Hacker Public Radio: 206 203 5729

The N Days of Christmas? Intro to Recreational Math
Part One: Counting Partridges and Gold Rings

First series on HPR that talks math, with attitude.
- Part Zero: Discussed Calendar Counting, where we learned to count
from the opening cocktail party, not the keynote.

- Part One: Advanced episode, where we start to count other things
* We are counting increasing sequences, so we need more than fingers
* There will be a couple of magical formulas at the end.
* I have created a spreadsheet version with the brute force table-
driven approach alongside the elegant formulas.

Inspired by a traditional Christmas song that is annoyingly repetitive,
but mathematically interesting. I will spare you the experience of
hearing me sing it, which would be painful on many levels.

Stepping Up to the Problem: We'll take a 4-step approach to the general
problem of the number of gifts given on the N Days of Christmas.

Step 0: A More Casual "True Love"
Rule: "You get a gift on Christmas Day, and that's it."
* Let's hope it is not a braised partridge with pear compote kit

Question: How many gifts will I have received on Day 1, Day 2, ...?
Answer: No brainer, right? Sequence is {1, 1, 1, 1, 1, 1, ...}

Step 1: A Devoted, Yet Frugal, True Love
Rule: "You get a gift for each Day of Christmas. One."

Question: <same>
Solution: Sequence is {1, 1+1, 1+1+1, ...}

Meta Comment: There's a pattern developing here. Maybe two patterns.
a) At the end of Day N, I have N gifts.
b) On any given Day, my total gift count is the running sum of the
cumulative gift counts from Step 0.

Still pretty easy, right?

Step 2: A Devoted and Generous True Love
Rule: "I will give you 1 gift on Day 1, 2 on Day 2, 3 on Day 3, etc.

* Observation: This is where the song comes in, with an increasing
sequence of daily gift volumes. The counting starts to get
more complicated. I'm starting to think of using a spreadsheet.

Question: What's the cumulative number of gifts on Days 1, 2, 3,...?
Solution: Let's review what this looks like.

On Day 1, I still have one gift.
On Day 2, I get two turtle doves, for a total of 3 gifts.
Day 3 brings three French hens, and 3 + 3 gives me 6 gifts.
Day 4 fetches four calling birds, for a total menagerie of 10

Wow! This could add up.

Meta Comment: Even though the counts pile up, I still see two patterns:

a) On Day N, I get N gifts. Daily gift counts are the finger-math counting
numbers from our Calendar Count episode: 1, 2, 3, 4, ..., 12.

b) The second pattern is becoming more apparent. The Step 2 cumulative
totals on Day N are the partial sums of the totals for Step 1.

The arithmetic may be getting to the point where I'll make some
mistakes in computing the partial sums in my head.

At this point, let's stop and open a spreadsheet program. We don't need
fancy functions, so any spreadsheet program would do it.
- My own spreadsheet for this show is available for a couple of formats.
* But the basics can be illustrated in my text show notes.
* We are building Pascal's Triangle, which you can find at:
http://www.mathisfun.com/pascals-triangle.html
http://en.wikipedia.com/wiki/Pascal's_triangle

* For background on Pascal's Triangle and the Binomial Theorem, see
the excellent videos by Sal Khan at KhanAcademy.org

- Basic setup: Initialization, assuming that we start in cell A1.
* Warning: We are taking the classic setup and tipping it sideways
- Rows are upward-pointing diagonals in the spreadsheet.
- Diagonals are the columns in the table
- I have truncated the classic Pascal's Triangle to 4 diagonals.
- The diagonals corresponds to Steps 0, 1, 2, 3.

* Construction:
- We need four cells with the value '1' in B1:E1
- We need a column of row numbers in column A, cells A1:A15 is plenty
A1 = 0, A2 = 1, A3 = 2, ..., A15 = 14 <-- these are row numbers
- Finally, we need a column of 1's in B1:B15

- Before we write anything else, we can mark Step 0 as solved in column B.

Here's where Observed Pattern (b) for Steps 1 and 2 pays off.
- Totals by Day for Step 1 are the running sums to date for Step 0.
for Step 2 are the running sums for Step 1.
for Step 3 are the running sums for Step 2.

* Let's set up a formula in Column C for running sums for B.
* When we like the way it works, we'll copy it to Columns D and E.

Solution Time: Running Sums in a Spreadsheet Table of Values

- There are two ways to define a running sum alongside a column of data
A. The Naive Approach: Set a base SUM() formula that is fixed at the
top, variable at the bottom, and copy it down the column.
* For Day k, this requires (k - 1) ADD operations
* Number of ADDs for the whole column is O(N * N).
- We'll find the exact number in a second.

B. The Think Recursively Approach:
* Insight: Sum(N things) = Sum(N - 1 things) + Thing(N)
When we copy the formula, the second formula will add Days 1 and 2.
The third formula will add Days 1 to 3, etc.

Naive Smart
Cell C1: =sum(B$1:B1) C1: =B1
C2: =sum(B$1:B2) C2: =C1 + B2
C3: =sum(B$1:B3) C3: =C2 + B3
... ...
C12: =sum(B$1:B12) C12: =C11 + B12 # Like 12th Day of New Years

Either one works. If you were to copy it to cells D1:D12 and E1:E12,
we'd have the answers to Steps 2 and 3 in the bag, as well.

Since I have brought in the magic of Pascal's Triangle, I will now invoke
some mathematical magic known as the Binomial Theorem to write down a
closed-form formula for the number of gifts in Steps 0, 1, 2, 3 for N
Days of Christmas.

Step 0: 1 gift Technically, this is (N - 1) "choose" 0, but who cares?

Step 1: N gifts = N "choose" 1, the number of ways to choose 1 item from
a set of N distinct objects, independent of order.

Step 2: Should produce (N + 1) choose 2 gifts. The shift to the higher
value of N results from taking the same number of steps along the
next diagonal in the Triangle.

Note: Don't make me prove it. That would make for a non-recreational
episode of HPR, to be sure.

To calculate N choose 2, we can either use the COMBIN(N, k) function
from Gnumeric, or we can use a fraction whose top and bottom portions
are defined using Countdown Product Math.

* COMBIN(N+1, 2) = 2-term countdown product, start @ (N+1) (N+1)*N
----------------------------------------- = --------
2-term countdown product start @ 2 2*1

* Check when N = 12: Gifts = 13*12/2 = 78. Equal to brute force sum.

* Aside: Number of ADDs for Naive Running Sum with 12 terms is the sum
of 0, 1, 2, ..., 11, or COMBIN(N, 2) = COMBIN(12,2) = 12*11/2 or 66.
- Take a look at Step 2, Day 11, and you'll see the total is 66.
- As the number of rows increases, this approaches N*N/2 ADD operations
- That's where the Big-O of N * N came from earlier.

Step 3: See below. But the answer is (N+2) choose 3, because we slipped into
the next diagonal down the triangle to pick up the running sums.

Formula = (N+2)*(N+1)*N / 6, where 6 = 3*2*1, the 3-fold countdown product
with start value of 3, aka "3 factorial".

Digression: Why The Naive Approach Could Be "Wrong" for You

- For small tables like the 12 Days of Christmas variants, meh.

- Do I care? Let's see how we like those Sums as the table grows.
12 rows ==> proportional to 12^2 (exactly 66, so factor's about 0.5)
100 rows ==> proportional to 10,000 (4950)
1000 rows ==> around 500,000
10000 rows ==> around 50 million ADDs
100000 rows ==> around 5 billion (5 thousand million) ADDs

Note: Comparing these numbers to (N - 1) ADDs, I prefer the recurrence
relation form of the running sum.

Big Take Home Idea: If you remember anything from this series, it
should be these two things:
1. Count from the opening cocktail party, not the keynote date.
2. I will think recursively. I will think recursively.

Back to the Gift-Summing Adventure

So, what was Step 3?

Step 3: Overzealous True Love (Gives the Countdown)
- In this case, the True Love heard the song being performed by a choir
* The Lover, who is really in love and wealthy, interprets the daily
rundown of "Four calling birds, three French hens, ..." as
a shopping list for the Day. She really runs up the gifting.

* She's giving a Partridge every day, two turtles from Day 2 on, etc.

* The other gifts sound like a nuisance, but the 40 gold rings. Hmm.
- Counting from the keynote, as I did in the closing of Episode Zero,
would have cost me 5 gold rings.
- Expensive lesson, that one.

Wow! That was a pretty easy ride to a problem that looked kind of
complicated at the beginning.
- To get the answers for more Days of Christmas, I could shut off the
player right now and just add rows to my spreadsheet.
- If I want to show off, I can use the general formulas

End of Episode, right? Well, there is One.. More.. Thing.

Homework Question: What if there were 72 Days of Christmas?
- How many gifts would be given in total for Steps 0, 1, 2 and 3?
- If you followed along, you can answer that in terms of the value.
- I can't guarantee that you can make anyone else care.

Happy Holidays! See you at the New Year's Eve show.

Contact: Charles in NJ
Email: catintp@yahoo.com

Charlie + Alpha + Tango + India + November + Tango + Papa.